package Solution101_200.problem105.PreorderandInorder;

import common.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/07/11 12:25
 */
public class BetterSolution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0 || inorder == null || preorder.length != inorder.length) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[0]);
        TreeNode current = root;
        int j = 0;
        Deque<TreeNode> stack = new ArrayDeque<>();

        for (int i = 1; i < preorder.length; i++) {
            if (current.val != inorder[j]) {
                stack.push(current);
                current.left = new TreeNode(preorder[i]);
                current = current.left;
            }
            else {
                j++;
                while (!stack.isEmpty() && stack.peek().val == inorder[j]) {
                    j++;
                    current = stack.pop();
                }
                current.right = new TreeNode(preorder[i]);
                current = current.right;
            }
        }

        return root;
    }
}
